import math
import random
import numpy as np

T1_Range = 0.8    # 聚类参数
T2_Range = 0.6
# 种群适应度
def Get_Population_Adaptability(Population_Member):
    print("模块：Cluster\t方法：Get_Population_Adaptability(Population_Member):")
    Adaptability = []   #  所有个体的目标值
    for i in range(len(Population_Member)):
        Temp = []
        Temp.append(Population_Member[i].Adaptability[0])
        Adaptability.append(Temp)
    return Adaptability

# 目标空间标准化  ----[[],[],...,[]]
def Normal_Object_Space(Population_Member):
    print("模块：Cluster\t方法：Normal_Object_Space(Population_Member):")
    Adaptability = Get_Population_Adaptability(Population_Member)   #  所有个体的目标值
    Normal_Population_Objection = []    # 种群个体在标准化空间的的目标值
    Object_Dim = []     # 记录每一维
    Object_Dim_Min = [] # 每一维的下界
    Object_Dim_Max = [] # 每一维的上界

    # 存储每一维目标
    for i in range(len(Adaptability[0])):
        Object_Dim.append([item[i] for item in Adaptability])
        # 如果一个类中目标值都是一样的 最大减去最小会生成0
        if min(Object_Dim[i]) != max(Object_Dim[i]):
            Object_Dim_Min.append(min(Object_Dim[i]))   # 获得ideal点
            Object_Dim_Max.append(max(Object_Dim[i]))
        else:
            Object_Dim_Min.append(min(Object_Dim[i]))   # 获得ideal点
            Object_Dim_Max.append(-1)            
        
        
    # 将解转换到理想点为原点的空间，方便进行标准化操作
    for i in range(len(Adaptability)):
        Normal_Population_Objection.append(
            ((np.array(Adaptability[i]) - np.array(Object_Dim_Min)) / 
            (np.array(Object_Dim_Max) - np.array(Object_Dim_Min))).tolist()
            )

    ##############################################################################
    #   参考NSGA-III
    #   n-1 维超平面方程还没得到，截距不一定得的到，目前只得到理想点基的坐标
    #   不除以截距，或可试除以(Max - Min)的比例
    ##############################################################################
    
    return Normal_Population_Objection


# 计算边界点 ---最靠近轴的点 ---[[],[],...,[]]
def Get_MaxDim_Dot(Dot_Ally):
    print("模块：Cluster\t方法：Get_MaxDim_Dot(Dot_Ally):")
    MaxDim_Dot = []         # 保存最靠近点坐标的下标
    for i in range(len(Dot_Ally[0])):
        Devide_Value = np.array([math.exp(-6)]*len(Dot_Ally[0]))   # 被除矩阵
        Devide_Value[i] = math.exp(0)
        
        # 保存每个归一化后除以[1,math.exp(-6),math.exp(-6)]的最大值 ... 计算最靠近点 
        Temp_Devide = []    
        for j in range(len(Dot_Ally)):
            Temp = np.array(Dot_Ally[j])
            Temp = Temp / Devide_Value
            Temp_Devide.append(max(Temp))

        MaxDim_Dot.append(Temp_Devide.index(min(Temp_Devide)))
    return MaxDim_Dot

# 归一化点集
def Get_MaxDim_Dot_Normalize(Population_Member):
    print("模块：Cluster\t方法：Get_MaxDim_Dot_Normalize(Population_Member):")
    Adaptability = Normal_Object_Space(Population_Member)
    return Get_MaxDim_Dot(Adaptability)

# 非归一化点集
def Get_MaxDim_Dot_Nunormalize(Population_Member):
    print("模块：Cluster\t方法：Get_MaxDim_Dot_Nunormalize(Population_Member):")
    Adaptability = Get_Population_Adaptability(Population_Member)
    return Get_MaxDim_Dot(Adaptability)


# 暂时不用，超平面难以构建 E的秩小于阶数 存在解靠近两个轴
# 计算超平面方程 ---目前以三维为例ax+by+cz+d=0
# 返回每维的截距
# 数学原理 ---点法式 https://blog.csdn.net/he11oworld/article/details/7912511
# a = ((p2.y-p1.y)*(p3.z-p1.z)-(p2.z-p1.z)*(p3.y-p1.y))
# b = ((p2.z-p1.z)*(p3.x-p1.x)-(p2.x-p1.x)*(p3.z-p1.z))
# c = ((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x))
# d = (0-(a*p1.x+b*p1.y+c*p1.z))
def Get_Equation_ThreeDim(Point1,Point2,Point3):   # [,,],[,,],[,,]
    print("模块：Cluster\t方法：Get_Equation_ThreeDim(Point1,Point2,Point3):")
    # 计算方程中的未知数
    a = ((Point2[1]-Point1[1])*(Point3[2]-Point1[2])-(Point2[2]-Point1[2])*(Point3[1]-Point1[1]))
    b = ((Point2[2]-Point1[2])*(Point3[0]-Point1[0])-(Point2[0]-Point1[0])*(Point3[2]-Point1[2]))
    c = ((Point2[0]-Point1[0])*(Point3[1]-Point1[1])-(Point2[1]-Point1[1])*(Point3[0]-Point1[0]))
    d = (0-(a*Point1[0]+b*Point1[1]+c*Point1[2]))
    # 计算每维截距
    Intercept = []
    Intercept.append(-(d/a))
    Intercept.append(-(d/b))
    Intercept.append(-(d/c))
    return Intercept


# 计算标准空间中两个解的距离[,,,],[,,,]
def Dist(member1,member2):
    print("模块：Cluster\t方法：Dist(member1,member2):")
    Euclidean_Distance = 0  # 欧式距离
    for i in range(len(member1)):
        Euclidean_Distance += math.pow((member1[i] - member2[i]), 2)
    Euclidean_Distance = math.sqrt(Euclidean_Distance)
    return Euclidean_Distance


# 计算阈值T1,T2
def Set_YU_Value(Population_Member):
    print("模块：Cluster\t方法：Set_YU_Value(Population_Member):")
    Adaptability = Normal_Object_Space(Population_Member)  # 先标准化目标空间
    Sum = 0  # 累加
    Member_Num = len(Population_Member) # 种群个体的数量
    for i in range(Member_Num):      # 所有解的距离
        if i != Member_Num - 1:
            for j in range(i+1,Member_Num):
                Sum += Dist(Adaptability[i],Adaptability[j])
    Sum = Sum / ((Member_Num * (Member_Num - 1))/2)
    T1 = Sum * T1_Range
    T2 = Sum * T2_Range
    return T1,T2


# 计算m个Cluster类的质心点 ---类的集合
def Set_Cluster_Center(Clusters,Adaptability):
    print("模块：Cluster\t方法：Set_Cluster_Center(Clusters,Adaptability):")
    Cluster_Center = []  # 类的质心点
    for i in range(len(Clusters)):
        Temp_Center = np.array([0.0]*len(Adaptability[0]))    # 记录每个类的总和
        Cluster_Content = Clusters[i]
        # 遍历此类中每一个元素
        for j in Cluster_Content:
            Temp_Center += np.array(Adaptability[j])
        # 取得均值--质心点
        Temp_Center = np.divide(Temp_Center, len(Cluster_Content))
        Cluster_Center.append(Temp_Center.tolist())
    return Cluster_Center


# 将所有个体按照质心点聚类
def Set_Member_Cluster(Cluster_Center,Adaptability,Population_Member):
    for i in range(len(Adaptability)):
        Temp_Dist = []          # 记录每个个体到质心点的距离 
        for j in range(len(Cluster_Center)):
            Temp_Dist.append(Dist(Cluster_Center[j], Adaptability[i]))
        Population_Member[i].Cluster_Index = Temp_Dist.index(min(Temp_Dist)) + 1


# k-means 迭代几次 ---有几个类就迭代几次
def K_Means(Cluster_Num,Adaptability,Population_Member):
    for i in range(Cluster_Num):
        Member_Cluster = [[] for m in range(Cluster_Num)]
        for j in range(len(Adaptability)):
            Member_Cluster[Population_Member[j].Cluster_Index - 1].append(j)

        Cluster_Center = Set_Cluster_Center(Member_Cluster,Adaptability)
        Set_Member_Cluster(Cluster_Center,Adaptability,Population_Member)


# 在标准化空间进行聚类
# 聚类
def Set_Population_Cluster(Population_Member):
    Adaptability = Normal_Object_Space(Population_Member)  # 先标准化目标空间
    T1,T2 = Set_YU_Value(Population_Member)   # 设置阈值T1,T2
    Cluster_Num = 0         # 类的数量
    Cluster_Center = []     # 类的质心点
    Cluster = []        # 类成员[[],[],...,[]]

    Sign = np.array([1]*len(Adaptability))     # 产生标记量，标记每个元素是否删除
    while 1 in Sign:        # 如果种群集中还有元素，就进行聚类
        Temp_Save = []       # 保存当前类的个体
        Cluster_Num = Cluster_Num + 1      # 将类数加1 

        # 从当前R中随机选择一个个体
        Temp_Sign = []      # 标记未删除个体的下标
        for i in range(len(Adaptability)):
            if Sign[i] == 1:
                Temp_Sign.append(i)
        Random_Index = random.sample(Temp_Sign, 1)
        Random_Choose = Adaptability[Random_Index[0]]    

        # 按照距离进行聚类
        for i in range(len(Adaptability)):
            if Sign[i] != 0:
                if Dist(Adaptability[i], Random_Choose) <= T1:
                    Temp_Save.append(i)
                    if Dist(Adaptability[i], Random_Choose) <= T2:
                        Sign[i] = 0
        
        Cluster.append(Temp_Save)
    Cluster_Center = Set_Cluster_Center(Cluster,Adaptability)
    Set_Member_Cluster(Cluster_Center,Adaptability,Population_Member)
    K_Means(Cluster_Num,Adaptability,Population_Member)
    Adjust_Cluster_Balance(Population_Member)


# 对聚类结果进行微调整
# 1.某些类样本不均衡,仅有一两个个个体
# 2.某个个体离种群太远,拉大平均距离导致聚成两类
# 3.由于k-means的调整甚至聚成空类
# 方法不均衡样本类随机被别的类融合
def Adjust_Cluster_Balance(Population_Member):
    Temp_Cluster = []   # 记录类
    for i in range(len(Population_Member)):
        Temp_Cluster.append(Population_Member[i].Cluster_Index)
    Cluster_Num = max(Temp_Cluster)
    Cluster_Member = [[] for m in range(Cluster_Num)]
    for i in range(len(Temp_Cluster)):
        Cluster_Member[Temp_Cluster[i] - 1].append(i)    
    
    # 剔除空类与不均衡类
    Cluster_With_Member = []     # 保留类下标-让后续个体随机加入
    for i in range(len(Cluster_Member)):
        if len(Cluster_Member[i]) > 2:
            Cluster_With_Member.append(i)  
    # 后续个体加入
    for i in range(len(Cluster_Member)):
        if len(Cluster_Member[i]) == 1 or len(Cluster_Member[i]) == 2: 
            for j in Cluster_Member[i]:
                Index = random.choice(Cluster_With_Member)
                Cluster_Member[Index].append(j)
    # 删除空类与不均衡类
    Index = 0
    while Index <= len(Cluster_Member) - 1:
        if len(Cluster_Member[Index]) <= 2:
            Cluster_Member.remove(Cluster_Member[Index])
            Index -= 1
        Index += 1
    # 把调整后的聚类结果重新输入种群
    for i in range(len(Cluster_Member)):
        Temp_Cluster = Cluster_Member[i]
        for j in Temp_Cluster:
            Population_Member[j].Cluster_Index = i + 1





